package leetcode_700;

import helpclass.TreeNode;

/**
 *@author 周杨
 *LongestUnivaluePath_687 给出一颗二叉树中节点值相同最大的路径
 *describe:用递归 AC 14%
 *2018年10月8日 上午10:36:05
 */
public class LongestUnivaluePath_687 {
	
	public static void main(String[] args) {
		LongestUnivaluePath_687 test=new LongestUnivaluePath_687();
		TreeNode root=new TreeNode(4);
		root.left=new TreeNode(4);
		root.right=new TreeNode(4);
		System.out.println(test.longestUnivaluePath(root));
	}
	int res=0;
	/**
	 * describe:不知道哪里错了
	 * 2018年10月8日 上午10:08:54
	 */
	public int longestUnivaluePath(TreeNode root) {
        if(root==null)
        	return 0;
        help(root,root.val);
        longestUnivaluePath(root.left);
        longestUnivaluePath(root.right);
        return res-1;//因为我算的是节点
    }
	
	public int help(TreeNode root,int target) {
		if(root==null)
			return 0;
		if(root.val==target) {
			//如果这样算 会重复计算两次本节点
			int now=1+help(root.left,target)+help(root.right,target);
			this.res=Math.max(res, now);
			return now;
		}
		return 0;
	}
	
	  public int longestUnivaluePath1(TreeNode root) {
	        helper(root);
	        return res;
	    }
	    
	    public int helper(TreeNode root) {
	        if (root == null) return 0;
	        
	        // Get longest path for children
	        int left = helper(root.left);
	        int right = helper(root.right);
	        
	        // MaxPath - maximum path with current node being root
	        int maxPath = 0;
	        
	        // result - value to be returned - maximum of only one path
	        int result = 0;
	        
	        // If left can be extended
	        if (root.left != null && root.left.val == root.val) {
	            maxPath += left+1;
	            result = left + 1;
	        }
	        
	        // If right can be extended
	        if (root.right != null && root.right.val == root.val) {
	            maxPath += right+1;
	            result = Math.max(result, right + 1);
	        }
	        
	        // Update global max path value
	        res = Math.max(res, maxPath);
	        
	        return result;
	    }
	
}
